package Sort;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.List;
import java.util.Stack;

/**
 * @Author: zhiping
 * @ClassName Dfs
 * @Date:2018/9/11 17:27
 * @Description: Depth First Search
 * 二叉树
 * 本例通过栈和遍历两种方式实现
 */
public class Dfs {

    private BinaryTreeNode headNode;

    /**
     * @MethodName initBinTree
     * @Date:2018/9/11 17:32
     * @Parm:[]
     * @Return:void
     * @Description: 构建一个二叉树
     */
    @Before
    public void initBinTree(){

        headNode = new BinaryTreeNode("A");
        BinaryTreeNode nodeB = new BinaryTreeNode("B");
        headNode.setLeft(nodeB);
        BinaryTreeNode nodeC = new BinaryTreeNode("C");
        headNode.setRight(nodeC);
        BinaryTreeNode nodeD = new BinaryTreeNode("D");
        BinaryTreeNode nodeE = new BinaryTreeNode("E");
        nodeB.setLeft(nodeD);
        nodeB.setRight(nodeE);
        BinaryTreeNode nodeI = new BinaryTreeNode("I");
        nodeE.setRight(nodeI);


        BinaryTreeNode nodeF = new BinaryTreeNode("F");
        BinaryTreeNode nodeG = new BinaryTreeNode("G");

        nodeC.setLeft(nodeF);
        nodeC.setRight(nodeG);
    }


    @Test
    public void statckSearch(){

        Stack<BinaryTreeNode> nodeTrack = new Stack<>();

        nodeTrack.push(headNode);

        while(!nodeTrack.isEmpty()){
            BinaryTreeNode tmpNode = nodeTrack.pop();
            System.out.println(tmpNode.getId());
            if(tmpNode.getRight()!=null){
                nodeTrack.push(tmpNode.getRight());
            }
            if(tmpNode.getLeft()!=null){
                nodeTrack.push(tmpNode.getLeft());
            }
        }

    }
    /**
     * @MethodName RecursiveSearch
     * @Date:2018/9/11 18:02
     * @Parm:[]
     * @Return:void
     * @Description: 递归实现
     *
     * A
     * B
     * D
     * E
     * I
     * C
     * F
     * G
     */
    @Test
    public void recursiveSearch(){
        recursiveSearchInner(headNode);
    }

    private void recursiveSearchInner(BinaryTreeNode tmpNode){
        System.out.println(tmpNode.getId());
        if(tmpNode.getLeft()!=null){
            recursiveSearchInner(tmpNode.getLeft());
        }
        if(tmpNode.getRight()!=null){
            recursiveSearchInner(tmpNode.getRight());
        }
    }
}

